题解 洛谷 P9118 [春季测试 2023] 幂次

P9118 [春季测试 2023] 幂次

简要题意

给定两个参数 $n,k$，问在区间 $[1,n]$ 中有多少正整数 $x$ 满足 $x = a^p$，其中 $p \ge k$。

策略分析

前置芝士：区间 $[1,n]$ 中完全平方数有 $\left \lfloor \sqrt{n} \right \rfloor $ 个，这个结论用整除分块很容易就可以证出来。

有了这个结论，我们就已经处理完了这个题中 $k=2$ 的情况了，我们来分析剩下的情况。

当 $k=1$ 时，显然区间内每个数都可以表示为 $a^1$，所以答案就是 $n$。

当 $k \ge 3$ 时，底数为 $1$ 的情况就直接跳过，我们发现现在底数最小是 $2$，而我们单次计算最大的可能次数就是 $\log_2 n$，本题中 $n \le 10^{18}$，所以单次最多计算次数为 $\left \lceil \log_2 10^{18} \right \rceil = 60$。所以我们直接暴力枚举就可以了。平方不需要枚举直接用我们的结论，我们从 $\left \lfloor \sqrt[3]{n} \right \rfloor $ 开始枚举即可，枚举到的数标记一下，下次如果标记过则计数器不操作，碰到完全平方数记一下最后把多算的这一次减掉就行。

参考代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#define LL unsigned long long
using namespace std;

namespace SHAWN {
    LL n, k, bcnt, ans, tmp, p;
    //tmp表示底数，p表示幂次，ans是答案，bcnt是重复计算的完全平方数
    map<LL, bool> m;
    int work()
    {
        cin >> n >> k;
        LL bk = sqrtl(n);
        // bk是[1,n]中完全平方数的数量
        for (LL i = 2; i * i * i <= n; ++i) {
            // 从三次根号下n开始枚举
            tmp = i * i; p = 2;
            while (tmp <= n/i) {
                tmp *= i; ++p;
                if (m[tmp] || p < k) { continue; }
                LL k = sqrtl(tmp);
                if (k * k == tmp) { ++bcnt; }
                m[tmp] = true; ++ans;
            }
        }
        if (k == 1) { cout << n << '\n'; }
        else if (k == 2) { cout << ans - bcnt + bk << '\n'; }
        else if (k >= 3) { cout << ans + 1 << '\n';}
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}

特别提醒

本题中要注意的是，开根的时候要用 sqrtl() 而不是 sqrt()，因为我们计算的对象和答案都是长长整型，用 sqrt() 可能会出错。